package org.example.myleet.p1719;

import java.util.*;

public class Solution {

    class MyNode {
        int value;
        HashSet<Integer> connectedNode;

        public MyNode(int value) {
            this.value = value;
            connectedNode = new HashSet<>();
        }
    }

    public int checkWays(int[][] pairs) {
        HashMap<Integer, MyNode> nodes = new HashMap<>(500);
        MyNode root = null;
        for (int[] pair : pairs) {
            MyNode node = nodes.getOrDefault(pair[0], new MyNode(pair[0]));
            node.connectedNode.add(pair[1]);
            nodes.put(pair[0], node);
            if (root == null) {
                root = node;
            } else if (root.connectedNode.size() < node.connectedNode.size()) {
                root = node;
            }
            node = nodes.getOrDefault(pair[1], new MyNode(pair[1]));
            node.connectedNode.add(pair[0]);
            nodes.put(pair[1], node);
            if (root.connectedNode.size() < node.connectedNode.size()) {
                root = node;
            }
        }
        if (root.connectedNode.size() < nodes.keySet().size() - 1) {
            //拥有最多连接节点的为根节点，但不能覆盖到每一个子节点
            return 0;
        }
        int result = 1;
        for (MyNode curNode : nodes.values()) {
            if (curNode == root) {
                continue;
            }
            int curDegree = curNode.connectedNode.size();
            MyNode parent = null;
            int parentDegree = Integer.MAX_VALUE;
            for (Integer neighbour : curNode.connectedNode) {
                MyNode neighbourNode = nodes.get(neighbour);
                if (neighbourNode.connectedNode.size() < parentDegree && neighbourNode.connectedNode.size() >= curDegree) {
                    //从相连接的节点中找到curNode的父节点，要满足neighbourNode边数大于等于curNode的边数，又要neighbourNode的边数尽量少
                    parent = neighbourNode;
                    parentDegree = parent.connectedNode.size();
                }
            }
            if (null == parent) {
                //找不到父节点
                return 0;
            }
            //下面还要验证父节点是否有效，要满足adj[curNode] ∈ adj[parent]，即当前节点的边是父节点的边的子集
            for (Integer neighbour : curNode.connectedNode) {
                if (neighbour == parent.value) {
                    continue;
                }
                if (!parent.connectedNode.contains(neighbour)) {
                    //无效父节点
                    return 0;
                }
            }
            if (parentDegree == curDegree) {
                //若满足 degree[curNode] == degree[parent] 则树的构造方式可以有多个
                result = 2;
            }
        }
        return result;
    }
}
